Insertion Sort Algorithm animation

Note

The Insertion sort algorithm is one of the key sorting algorithms used in Computer Science. To start with, the algorithm considers the first value of a list as a sorted sub-list (of one value to start with). This iterative algorithm then checks each value in the remaining list of values one by one. It inserts the value into the sorted sub-list of the data set in the correct position, moving higher ranked elements up as necessary.

This algorithm is an O(n2) algorithm which is relatively efficient for small lists and mostly sorted lists, and is often used as part of more sophisticated algorithms.

import turtle
from random import shuffle
from time import sleep

myPen = turtle.Turtle()
turtle.tracer(0)
myPen.speed(0)
myPen.color("#000000")
myPen.hideturtle()

topLeft_x = -180
topLeft_y = 120
intDim = 30
gap = 40

def text(message, x, y, size):
    FONT = ('Arial', size, 'normal')
    X = myPen.xcor()
    Y = myPen.ycor()
    myPen.penup()
    myPen.goto(x, y)
    myPen.color("#000000")
    myPen.write(message, align="left", font=FONT)
    myPen.goto(X, Y)
    myPen.pendown()

def display_code():
    global topLeft_x, topLeft_y
    offset_x = 30
    font_size = 14
    text("def insertion_sort(A):", topLeft_x - offset_x, topLeft_y + 420, font_size)
    text("    numberOfIterations = 1", topLeft_x - offset_x, topLeft_y + 390, font_size)
    text("    for i in range(1, len(A)):", topLeft_x - offset_x, topLeft_y + 360, font_size)
    text("        j = i - 1", topLeft_x - offset_x, topLeft_y + 330, font_size)
    text("        key = A[i]", topLeft_x - offset_x, topLeft_y + 300, font_size)
    text("        while (A[j] > key) and (j >= 0):", topLeft_x - offset_x, topLeft_y + 270, font_size)
    text("            # swap values", topLeft_x - offset_x, topLeft_y + 240, font_size)
    text("            A[j + 1] = A[j]", topLeft_x - offset_x, topLeft_y + 210, font_size)
    text("            j -= 1", topLeft_x - offset_x, topLeft_y + 180, font_size)
    text("        A[j + 1] = key", topLeft_x - offset_x, topLeft_y + 150, font_size)
    text("        numberOfIterations += 1", topLeft_x - offset_x, topLeft_y + 120, font_size)

# A procedure to draw the grid on screen using Python Turtle
def drawList(list, numberOfIterations):
    global topLeft_x, topLeft_y, intDim
    myPen.penup()
    myPen.goto(topLeft_x, topLeft_y)
    myPen.pendown()

    for i in range(0, len(list)):
        # myPen.goto(topLeft_x+i*intDim,topLeft_y-intDim)
        if i < numberOfIterations:
            myPen.fillcolor("#FF00FF")
        else:
            myPen.fillcolor("#FFFFFF")

        myPen.begin_fill()
        for side in range(0, 4):
            myPen.forward(intDim)
            myPen.left(90)
        myPen.end_fill()

        myPen.forward(intDim)
        text(list[i], topLeft_x + i * intDim + 8, topLeft_y, 20)


def highlightValue(list, position, color):
    global topLeft_x, topLeft_y, intDim, gap
    myPen.penup()
    myPen.goto(topLeft_x + position * intDim, topLeft_y + gap)
    myPen.pendown()
    myPen.fillcolor(color)
    myPen.begin_fill()
    for side in range(0, 4):
        myPen.forward(intDim)
        myPen.left(90)
    myPen.forward(intDim)
    myPen.end_fill()
    myPen.end_fill()

    text(list[position], topLeft_x + position * intDim + 8, topLeft_y + gap, 20)
    myPen.getscreen().update()
    sleep(0.2)

# A function to sort a list using an insertion Sort Algorithm
def insertionSort(list):
    global topLeft_y, intDim, gap

    drawList(list, 1)
    topLeft_y = topLeft_y - gap
    myPen.getscreen().update()
    sleep(1)

    numberOfIterations = 1

    display_code()                  # after topLeft_y in drawList

    for i in range(1, len(list)):
        highlightValue(list, i, "#FFAAFF")
        highlightValue(list, i, "#FFFFFF")
        j = i - 1
        key = list[i]
        while (list[j] > key) and (j >= 0):
            highlightValue(list, j, "#CCCCCC")
            list[j + 1] = list[j]
            highlightValue(list, j, "#FF00FF")
            j -= 1
        list[j + 1] = key
        numberOfIterations += 1
        drawList(list, numberOfIterations)
        topLeft_y = topLeft_y - gap
        myPen.getscreen().update()
        sleep(0.5)
    text("Insertion Sort Complete", topLeft_x, topLeft_y, 16)
    text("Number of Iterations: " + str(numberOfIterations), topLeft_x, topLeft_y - 30, 16)
    myPen.getscreen().update()

def main():
    list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    shuffle(list)
    my_win = turtle.Screen()
    insertionSort(list)
    my_win.exitonclick()

if __name__ == "__main__":
    main()
    mainloop()

See also

html://www.101computing.net/insertion-sort-algorithm/